from typing import Any, Iterator, Optional, Set, Tuple
from dataclasses import dataclass, field
from math import inf


@dataclass
class OutEdge:
    end: int
    data: Any


@dataclass
class LinkInfo:
    capacity: int
    flows: Set[int] = field(default_factory=set)
    # deleted: bool = False


class Graph:
    def __init__(self, num_vertices: int):
        self._edges = [{} for i in range(num_vertices)]

    def add_edge(self, start: int, end: int, data: Any = True) -> None:
        self._edges[start][end] = data

    def get_edge_data(self, start: int, end: int) -> Optional[Any]:
        return self._edges[start].get(end)

    def get_out_edges(self, start: int) -> Iterator[OutEdge]:
        d = self._edges[start]
        for k in d:
            yield OutEdge(end=k, data=d[k])

    def get_num_vertices(self) -> int:
        return len(self._edges)


eps = 1e-3


def find_min_link(g: Graph, flows_status) -> Tuple[LinkInfo, float]:
    num_vertices = g.get_num_vertices()
    min_cap = inf
    min_link = None
    for start in range(num_vertices):
        for i in g.get_out_edges(start):
            data: LinkInfo = i.data
            num_flows = sum(flows_status[k] for k in data.flows)
            if num_flows == 0:
                continue
            cap = data.capacity / num_flows
            if cap < min_cap:
                min_cap = cap
                min_link = data
    return min_link, min_cap


def solve(g: Graph, flows):
    num_vertices = g.get_num_vertices()
    flows_status = {k: 1 for k in flows}

    for k in flows:
        v = flows[k]
        for i in range(len(v) - 1):
            link_info: LinkInfo = g.get_edge_data(v[i], v[i+1])
            link_info.flows.add(k)

    flows_left = {k: 0 for k in flows}
    solution = {}

    while flows_left:
        _, cap = find_min_link(g, flows_status)
        for k in flows_left:
            flows_left[k] += cap
        links_to_remove = []
        for start in range(num_vertices):
            for i in g.get_out_edges(start):
                data: LinkInfo = i.data
                num_flows = sum(flows_status[k] for k in data.flows)
                if num_flows == 0:
                    continue
                data.capacity -= cap * num_flows
                if abs(data.capacity) < eps:
                    links_to_remove.append(data)
        for i in links_to_remove:
            for j in i.flows:
                if j in flows_left:
                    solution[j] = flows_left[j]
                    flows_left.pop(j)
                    flows_status[j] = 0
    return solution
